#include <iostream>
#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <stack>
 
using namespace std;
typedef long long ll;
const int N = 100005;
int a[N];
vector<int> b;

void insert(int x, int l, int r){
	int mid = (l + r)/2;
	if(b.empty()){
		b.push_back(x);
	}else if(l == r){
		if(x < b.at(mid)){
			b.insert(b.begin() + mid, x);
		}else{
			b.insert(b.begin() + mid+1, x);
		}
	}else if(x >= b.at(mid) && x <= b.at(mid+1)){
		b.insert(b.begin() + mid+1, x);
	}else if(x < b.at(mid)){
		insert(x, l, mid);
	}else if(x > b.at(mid)){
		insert(x, mid+1, r);
	}
}
 
int main() {
    int t, n;
    scanf("%d", &t);
    while(t--){
    	b.clear();
		scanf("%d", &n);
		for(int i=0;i<n;i++){
			scanf("%d", &a[i]);
			insert(a[i], 0, i-1);
			if((i+1) % 2 == 1){
				printf("%d ", b.at(b.size()/2));
			}
		}
		printf("\n");
	}
    return 0;
}
